package huawei.js2025;

/**
 * 没有回文串
 */
public class Question3 {



    public String next(int N, String s) {
        char[] charArray = s.toCharArray();

        for (int i = charArray.length - 1; i >= 0; i--) {
            char c = charArray[i];

            for (int j = c + 1; j < 'a' + N; j++) {
                if (isValid(charArray, i, (char) j)) {
                    charArray[i] = (char) j;
                    for (int k = i + 1; k < charArray.length; k++) {
                        for (int l = 'a'; l < 'a' + N; l++) {
                            if (isValid(charArray, k, (char) l)) {
                                charArray[k] = (char) l;
                                break;
                            }
                        }
                    }

                    if (!hasSubPalindrome(charArray)) {
                        return String.valueOf(charArray);
                    }
                }
            }
        }

        return "NO";
    }

    public boolean isPalindrome(char[] chars, int left, int right) {
        if (left < 0 || right > chars.length - 1) {
            return false;
        }

        while (left < right) {
            if (chars[left] != chars[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public boolean isValid(char[] chars, int index, char c) {
        if (index > 0 && chars[index - 1] == c) {
            return false;
        }

        if (index > 1 && chars[index - 2] == c) {
            return false;
        }

        return true;
    }

    public boolean hasSubPalindrome(char[] chars) {
        // 检测长度大于等于2的子串是否是回文
        for (int len = 2; len < chars.length - 2; len++) {
            for (int start = 0; start < chars.length - len; start++) {
                if (isPalindrome(chars, start, start + len)) {
//                    System.out.println(start + "_" + (start + len));
//                    System.out.println(s.substring(start, start + len + 1));
                    return true;
                }
            }
        }
        return false;
    }

    public void dfs (int N, String s) {
        while (!s.equals("NO")) {
            s = next(N, s);
            System.out.println(s);
        }
    }

    public static void main(String[] args) {
        Question3 q = new Question3();
        System.out.println();
        q.dfs(3, "aaa");
    }
}
